package com.geek.sort;

/**
 * 归并排序法
 * 简单来说就是二分排序法
 */
public class MergeSort {

	public static void main(String[] args) {
		int[] arr = new int[]{10,5,3,2,4,8,6,7};

		MergeSort mergeSort = new MergeSort();
		mergeSort.mergeSort(arr, 0, arr.length);

		printArr(arr);
	}

	private void mergeSort(int[] arr, int start, int end) {
		if(end > start){
			int middle = (end + start) / 2;
//			System.out.println(start+","+middle+","+end);

			this.mergeSort(arr, start, middle);
			this.mergeSort(arr, middle+1, end);

			this.merge(arr, start, middle, end);
		}
	}

	private void merge(int[] arr, int start, int middle, int end){
		if(end - start < 1){
			return;
		}
		System.out.println("下标值："+start+","+middle+","+end);

		System.out.print("交换前的值:");
		for (int k = start; k < end; k++) {
			System.out.print(arr[k] + ",");
		}
		System.out.println();

		int[] arr1 = new int[middle-start];
		int[] arr2 = new int[end-middle];
		int z = 0;
		for (int k = start; k < middle; k++) {
			arr1[z++] = arr[k];
		}
		z = 0;
		for (int k = middle; k < end; k++) {
			arr2[z++] = arr[k];
		}

		z = start;
		int i = 0;
		int j = 0;
		while (i < middle-start && j<end-middle){
			if(arr1[i] < arr2[j]){
				arr[z] = arr1[i++];
			}else{
				arr[z] = arr2[j++];
			}
			z++;
		}
		while (i < middle-start){
			arr[z++] = arr1[i++];
		}
		while (j < end-middle){
			arr[z++] = arr2[j++];
		}

		System.out.print("交换后的值:");
		for (int k = start; k < end; k++) {
			System.out.print(arr[k] + ",");
		}
		System.out.println();
		System.out.println("---------------------");
	}

	private static void printArr(int[] arr){
		for (int value : arr) {
			System.out.print(value + ",");
		}
		System.out.println();
	}

}
